
public class Fib
{

    public Fib()
    {

    }

    //动态规划
    public int DynamicFib(int n)
    {
        if (n < 2) return n;
        int[] dp = new int[2] { 0, 1 };
        for (int i = 2; i <= n; i++)
        {
            int temp = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return dp[1];
    }

    // 递归解法
    public int RecruitionFib(int n)
    {
        if (n < 2)
        {
            return n;
        }
        return RecruitionFib(n - 1) + RecruitionFib(n - 2);
    }

    // 第一种解法
    public int Solution(int n)
    {
        if (n < 2)
        {
            return n;
        }
        int p = 0, q = 0, temp = 1;
        for (int i = 2; i <= n; i++)
        {
            p = q;
            q = temp;
            temp = p + q;
        }
        return temp;
    }
}